package snippets.cse524.activeDates;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.apache.commons.collections.CollectionUtils;
import org.apache.commons.collections.Predicate;
import org.apache.commons.collections.Transformer;
import org.apache.commons.lang3.StringUtils;

import snippets.utils.Utils;

public final class ReReconstructChain {
	private static final int CHAIN_LENGTH = 3;
	private static Map<String, String> canonicalNames = new HashMap<String, String>();

	/**
	 * @param args
	 * @throws FileNotFoundException
	 */
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		if (args.length > 1) {
			System.err.print("Reading canonical names ... ");
			readCanonicalNames(new File(args[1]));
			System.err.println("done.");
		}

		Map<Set<String>, List<List<Link>>> chainByProfession = readOfficeChains(new FileReader(
				new File(args[0])));

		Map<Integer, Integer> countHistogram = new HashMap<Integer, Integer>();

		Map<Set<String>, List<Link>> compressedChains = new HashMap<Set<String>, List<Link>>();

		for (Set<String> profession : chainByProfession.keySet()) {
			List<List<Link>> chain = chainByProfession.get(profession);
			List<Link> compressed = compress(chain);
			compressedChains.put(profession, compressed);
		}

		compressedChains = compress(compressedChains);

		for (Set<String> profession : compressedChains.keySet()) {
			List<Link> compressed = compressedChains.get(profession);
			printAChain(profession, compressed, 1);

			if (!countHistogram.containsKey(compressed.size())) {
				countHistogram.put(compressed.size(), 0);
			}

			countHistogram.put(compressed.size(),
					countHistogram.get(compressed.size()) + 1);
		}

		for (Integer key : countHistogram.keySet()) {
			System.out.println(key + "\t" + countHistogram.get(key));
		}
	}

	public static Map<Set<String>, List<Link>> compress(
			Map<Set<String>, List<Link>> officeChains) {
		int numOffices = officeChains.keySet().size();
		int prevNumOffices = numOffices + 1;

		while (prevNumOffices != numOffices) {
			List<Set<String>> offices = new ArrayList<Set<String>>(
					officeChains.keySet());

			compressLoop: for (Set<String> officeLeft : offices) {
				for (Set<String> officeRight : offices) {
					if (officeLeft.equals(officeRight))
						continue;

					if (!officeChains.containsKey(officeLeft)
							|| !officeChains.containsKey(officeRight)) {
						continue;
					}

					Set<String> intersectedOffice = new HashSet<String>(
							officeLeft);
					intersectedOffice.retainAll(officeRight);

					List<Link> overlapped = overlapApproximate(
							officeChains.get(officeLeft),
							officeChains.get(officeRight));

					if (null != overlapped && overlapped.size() > 0
							&& intersectedOffice.size() > 0) {
						officeChains.remove(officeLeft);
						officeChains.remove(officeRight);

						Set<String> newKey = new HashSet<String>();
						newKey.addAll(officeLeft);
						newKey.addAll(officeRight);

						System.err.println("Merged ["
								+ StringUtils.join(officeLeft, " ") + "] and ["
								+ StringUtils.join(officeRight, " ")
								+ "] due to ["
								+ StringUtils.join(overlapped, " ") + "].");
						officeChains.put(newKey, overlapped);

						// break compressLoop;
					}
				}
			}

			prevNumOffices = numOffices;
			numOffices = officeChains.keySet().size();

			System.err.println("Went from " + prevNumOffices + " to "
					+ numOffices + ".");
		}

		return officeChains;
	}

	private static List<Link> compress(List<List<Link>> chain) {

		int currentSize = chain.size();
		int prevSize = currentSize + 1;

		while (prevSize != currentSize) {
			merge: for (int left = 0; left < chain.size(); ++left) {
				for (int right = 0; right < chain.size(); ++right) {
					if (left == right) {
						continue;
					}

					List<Link> leftList = chain.get(left);
					List<Link> rightList = chain.get(right);

					List<Link> overlapped = overlapApproximate(leftList,
							rightList);

					if (null != overlapped && overlapped.size() > 0) {
						chain.remove(leftList);
						chain.remove(rightList);

						chain.add(overlapped);
						break merge;
					}
				}
			}

			prevSize = currentSize;
			currentSize = chain.size();
		}

		List<Link> result = new ArrayList<Link>();

		for (List<Link> part : chain) {
			result = mergeApproximate(result, part);
		}

		for (int i = 0; i < result.size() - 1; ++i) {
			Link current = result.get(i);
			Link next = result.get(i + 1);

			if (current.equalsByTitle(next)) {
				if (current.within(next) || next.within(current)) {
					result.remove(current);
					result.remove(next);

					result.add(
							i,
							new Link(current.title, Math.min(current.beginYear,
									next.beginYear), Math.max(current.endYear,
									next.endYear)));
				}
			}
		}

		return result;
	}

	private static void printChains(Map<String, List<List<Link>>> officeChains) {
		for (String office : officeChains.keySet()) {
			// System.err.println("Looking for " + office);
			List<List<Link>> chains = officeChains.get(office);

			printAChain(office, chains);
		}
	}

	private static void printAChain(String office, List<List<Link>> chains) {

		System.out.println(office.toUpperCase());

		List<String> parts = new ArrayList<String>();

		for (List<Link> chain : chains) {
			System.out.println(StringUtils.join(CollectionUtils
					.transformedCollection(chain, new Transformer() {

						@Override
						public Object transform(Object link) {
							// TODO Auto-generated method stub
							return ((Link) (link)).toString();
						}
					}), " | "));
		}

		// System.out.println(StringUtils.join(parts, "\t"));
		System.out.println();

		return;
	}

	private static void printAChain(Set<String> _office, List<Link> chain,
			int dummy) {

		List<String> officeWords = new ArrayList<String>(_office);
		Collections.sort(officeWords);

		System.out.println(StringUtils.join(officeWords, " ").toUpperCase());

		List<String> parts = new ArrayList<String>();

		System.out.println(StringUtils.join(
				CollectionUtils.transformedCollection(chain, new Transformer() {

					@Override
					public Object transform(Object link) {
						// TODO Auto-generated method stub
						return ((Link) (link)).toString();
					}
				}), " | "));

		// System.out.println(StringUtils.join(parts, "\t"));
		System.out.println();

		return;
	}

	private static void readCanonicalNames(File input)
			throws FileNotFoundException {
		Scanner in = new Scanner(input);

		while (in.hasNextLine()) {
			String line = in.nextLine().trim();

			String[] parts = StringUtils.split(line);

			if (parts.length != 3) {
				System.err.println("Invalid canonical name line : "
						+ StringUtils.join(parts, " ## "));
				continue;
			}

			String left = StringUtils.join(StringUtils.split(parts[0], '_'),
					' ').toLowerCase();

			canonicalNames.put(left, parts[1]);
		}
	}

	private static Map<Set<String>, List<List<Link>>> readOfficeChains(
			Reader input) {
		Scanner in = new Scanner(input);
		Map<Set<String>, List<List<Link>>> officeChains = new HashMap<Set<String>, List<List<Link>>>();

		while (in.hasNextLine()) {
			String line = in.nextLine();

			String[] parts = StringUtils.split(line, '\t');
			for (int i = 1; i < parts.length; ++i) {
				String part = parts[i].toLowerCase();
				// check if there's a canonical name for this guy

				part = part.replace("acting", "").replaceAll("\\.", "").trim();

				parts[i] = canonicalNames.containsKey(part.toLowerCase()) ? canonicalNames
						.get(part.toLowerCase()) : part;
			}

			if (parts.length != CHAIN_LENGTH + 2) {
				continue;
			}

			Pattern year = Pattern.compile("([0-9]{4})");
			Matcher yearMatcher = year.matcher(parts[1]);

			int minYear = Integer.MAX_VALUE;
			int maxYear = Integer.MIN_VALUE;

			while (yearMatcher.find()) {
				int thisYear = Integer.parseInt(yearMatcher.group());

				if (thisYear < minYear)
					minYear = thisYear;
				if (thisYear > maxYear)
					maxYear = thisYear;
			}

			if (minYear == Integer.MAX_VALUE)
				minYear = -1;
			if (maxYear == Integer.MIN_VALUE)
				maxYear = -1;

			String _office = parts[0].replaceAll("\\'", "").trim()
					.toLowerCase();

			Set<String> officeWordSet = new HashSet<String>();
			for (String officeWord : StringUtils.split(_office, " ;,	\n")) {
				officeWordSet.add(officeWord);
			}
			officeWordSet.removeAll(Utils.StopwordSet);

			if (!officeChains.containsKey(officeWordSet)) {
				officeChains.put(officeWordSet, new ArrayList<List<Link>>());
			}

			Link left = new Link(parts[2], -1, minYear);
			Link mid = new Link(parts[3], minYear, maxYear);
			Link right = new Link(parts[4], maxYear, -1);

			List<Link> list = new ArrayList<Link>(3);
			list.add(left);
			list.add(mid);
			list.add(right);

			list = new ArrayList<Link>(CollectionUtils.select(list,
					new Predicate() {
						@Override
						public boolean evaluate(Object link) {
							// TODO Auto-generated method stub
							return !((Link) (link)).title.equals("nobody");
						}
					}));

			officeChains.get(officeWordSet).add(list);
		}

		return officeChains;
	}

	public static List<Link> overlapApproximate(List<Link> left,
			List<Link> right) {
		// System.err.println("CHECKING " + StringUtils.join(left, ", ") +
		// " and " + StringUtils.join(right, ", "));

		for (int loc = 0; loc < left.size(); ++loc) {
			int leftEnd = Math.min(loc + right.size(), left.size());
			int rightEnd = Math.min(right.size(), left.size() - loc);

			List<Link> leftPart = left.subList(loc, leftEnd);
			List<Link> rightPart = right.subList(0, rightEnd);

			// System.err.println("CHECKING PART " + StringUtils.join(leftPart,
			// ", ") + " and " + StringUtils.join(rightPart, ", "));

			assert (leftPart.size() == rightPart.size());

			boolean match = true;
			for (int i = 0; i < leftPart.size(); ++i) {
				if (!leftPart.get(i).equalsApproximate(rightPart.get(i))) {
					match = false;
					break;
				}
			}

			List<Link> laterParts = right.subList(rightEnd, right.size());
			List<Link> earlyParts = left.subList(0, loc);

			if (match) {
				checkLoop: for (Link later : laterParts) {
					for (Link early : earlyParts) {
						if (later.before(early)) {
							match = false;
							break checkLoop;
						}
					}
				}
			}

			if (match) {

				// System.err.println("Overlap between "
				// + StringUtils.join(left, ", ") + " and "
				// + StringUtils.join(right, ", ") + " : "
				// + (left.size() - loc));
				// return merge(leftPart, rightPart);

				List<Link> result = new ArrayList<Link>();

				result.addAll(earlyParts);
				result.addAll(mergeOverlapped(leftPart, rightPart));
				result.addAll(laterParts);

				// System.err.println("Returning "
				// + StringUtils.join(result, ", "));
				// System.err.println();

				return result;
			}
		}

		// System.err.println("No overlap between " + StringUtils.join(left,
		// ", ") + " and " + StringUtils.join(right, ", "));
		return null;
	}

	public static List<Link> mergeOverlapped(List<Link> left, List<Link> right) {
		assert (left.size() == right.size());

		List<Link> result = new ArrayList<Link>();

		for (int i = 0; i < left.size(); ++i) {
			Link leftPart = left.get(i);
			Link rightPart = right.get(i);

			assert (leftPart.equalsByTitle(rightPart));

			Link newLink = mergedLink(leftPart, rightPart);

			result.add(newLink);
		}

		return result;
	}

	private static Link mergedLink(Link leftPart, Link rightPart) {
		int begin = leftPart.beginYear == -1 ? rightPart.beginYear
				: leftPart.beginYear;
		int end = leftPart.endYear == -1 ? rightPart.endYear : leftPart.endYear;
		Link newLink = new Link(leftPart.title, begin, end);
		return newLink;
	}

	public static List<Link> mergeApproximate(List<Link> left, List<Link> right) {
		List<Link> result = new ArrayList<Link>();

		// System.err.println("Merging " + StringUtils.join(left, ", ") +
		// " AND "
		// + StringUtils.join(right, ", ") + ".");

		int leftLoc = 0;
		int rightLoc = 0;

		searchLoop: while (leftLoc < left.size() && rightLoc < right.size()) {
			Link leftPart = left.get(leftLoc);
			Link rightPart = right.get(rightLoc);

			// System.err.println("At " + leftLoc + ", " + rightLoc);

			if (leftPart.equalsApproximate(rightPart)) {
				result.add(mergedLink(leftPart, rightPart));
				// System.err.println("Adding merged: "
				// + result.get(result.size() - 1));
				++leftLoc;
				++rightLoc;

				continue;
			}

			if (leftPart.before(rightPart)) {
				result.add(leftPart);
				// System.err.println("Adding left: " + leftPart);
				++leftLoc;

				continue;
			}

			if (rightPart.before(leftPart)) {
				result.add(rightPart);
				// System.err.println("Adding right: " + rightPart);
				++rightLoc;

				continue;
			}
			// we need dp to merge, but let us do some heuristics.

			{ // enforcing blocks
				int leftSearch = leftLoc + 1;

				while (leftSearch < left.size()
						&& !rightPart.before(left.get(leftSearch))) {
					if (rightPart.equalsApproximate(left.get(leftSearch))) {
						result.add(leftPart);
						// System.err.println("Right " + rightPart
						// + " matched on left list, adding left "
						// + leftPart);
						++leftLoc;

						continue searchLoop;
					}

					if (left.get(leftSearch).before(rightPart)) {
						// System.err.println("Found " + left.get(leftSearch)
						// + " before " + rightPart
						// + ", adding all upto it.");
						result.addAll(left.subList(leftLoc, leftSearch));
						leftLoc = leftSearch;
						continue searchLoop;
					}

					++leftSearch;
				}

				if (leftSearch < left.size()) {
					// right part was before left part somewhere on the list
					// System.err.println(rightPart + " was before "
					// + left.get(leftSearch) + ", adding it.");
					result.add(rightPart);
					result.addAll(left.subList(leftLoc, leftSearch));
					leftLoc = leftSearch;
					++rightLoc;
					continue searchLoop;
				}
			}

			{ // enforcing blocks
				int rightSearch = rightLoc + 1;
				while (rightSearch < right.size()
						&& !leftPart.before(right.get(rightSearch))) {
					if (leftPart.equalsApproximate(right.get(rightSearch))) {
						// System.err.println("Left " + leftPart
						// + " matched on right list, adding right "
						// + rightPart);
						result.add(rightPart);
						++rightLoc;

						continue searchLoop;
					}

					if (right.get(rightSearch).before(leftPart)) {
						// System.err.println("Found " + right.get(rightSearch)
						// + " before " + leftPart
						// + ", adding all upto it.");
						result.addAll(right.subList(rightLoc, rightSearch));
						rightLoc = rightSearch;
						continue searchLoop;

					}

					++rightSearch;
				}

				if (rightSearch < right.size()) {
					// System.err.println(leftPart + " was before "
					// + right.get(rightSearch) + ", adding it.");
					result.add(leftPart);
					result.addAll(right.subList(rightLoc, rightSearch));
					rightLoc = rightSearch;
					++leftLoc;
					continue searchLoop;
				}
			}

			// if we are here, we couldn't find anything. Just add both.
			// System.err.println("Couldn't match, adding both " + leftPart +
			// ", "
			// + rightPart + ".");

			result.add(leftPart);
			result.add(rightPart);

			++leftLoc;
			++rightLoc;

		}

		if (leftLoc < left.size()) {
			result.addAll(left.subList(leftLoc, left.size()));
		}

		if (rightLoc < right.size()) {
			result.addAll(right.subList(rightLoc, right.size()));
		}

		// System.err.println("Returning " + StringUtils.join(result, ", ") +
		// ".");
		// System.err.println();
		return result;
	}
}
